package ysf.com.sort;

import com.alibaba.fastjson.JSON;

/**
 * @author ysf
 * @version 1.0
 * @date 2021/12/11 15:45
 *
 *  基数排序
 *
 */
public class RadixSort {


    public static void main(String[] args) {

        int[] arrys = {10,5,6,2,1,8,3,9,12,15};
        System.out.println(JSON.toJSONString(arrys));
        radixSort(arrys);
        System.out.println(JSON.toJSONString(arrys));

    }

    /**
     * 基数排序
     * @param arrys
     */
    public static void radixSort(int[] arrys){

        // 存放数组中最大的数字
        int max = Integer.MAX_VALUE;
        for (int value : arrys) {
            if (value > max) {
                max = value;
            }
        }

        // 计算最大数字是几位数
        int maxLength = (max + "").length();
        // 用于临时存储数据
        int[][] temp = new int[10][arrys.length];
        // 用于记录在 temp 中相应的下标存放数字的数量
        int[] counts = new int[10];
        // 根据最大长度的数决定比较次数
        for (int i = 0 , n = 1; i <maxLength ;i++, n*=10) {
            // 每一个数字分别计算余数
            for (int j = 0;j < arrys.length; j++) {
                // 计算余数
                int remainder = arrys[j] / n % 10;
                // 把当前遍历的数据放到指定的数组中去
                temp[remainder][counts[remainder]] = arrys[j];
                // 记录数量
                counts[remainder]++;
            }
            // 记录取的元素需要放的位置
            int index = 0;

            // 把数字 取出来
            for (int k = 0; k < counts.length; k++) {
                // 记录数量的数组中当前余数记录的数量不为0
                if (counts[k] != 0) {
                    // 取出循环元素

                    for (int l = 0; l < counts[k];l++){
                        arrys[index] = temp[k][l];
                        // 记录下一个位置
                        index++;
                    }
                    // 把数量清空
                    counts[k] = 0;
                }
            }
        }
    }

}
